//@题目链接https://leetcode.cn/problems/find-mode-in-binary-search-tree/

//递归中序解法
class Solution {
public:
    void dfs(TreeNode* root,vector<int>& ivec,int& pre,int& maxCount,int& count){
        if(root == nullptr) return;
        dfs(root->left,ivec,pre,maxCount,count);
        //第一个节点的情况
        if(pre == -INT_MAX)  count=1;
        else if(pre == root->val)    count++;
        else count = 1;
        pre = root->val;
        //切记count 与 maxCount关系的更新要在每次访问节点的时候处理
        //如果每次访问到不同的节点才处理的话就需要更复杂的逻辑
        if(count == maxCount){
            ivec.push_back(pre);
        }
        if(count > maxCount){
            maxCount = count;
            ivec.clear();
            ivec.push_back(pre);
        }
        dfs(root->right,ivec,pre,maxCount,count);
    }
void dfs(TreeNode* root,vector<int>& ivec,int& pre,int& maxCount,int& count){
        if(root == nullptr) return;
        dfs(root->left,ivec,pre,maxCount,count);
        if(pre == root->val)    count++;
        else{
            count = 1;
            pre = root->val;
        }
        if(count>maxCount){
            ivec.clear();
            maxCount = count;
            ivec.push_back(root->val);
        } else if(count == maxCount){
            ivec.push_back(root->val);
        }  
        dfs(root->right,ivec,pre,maxCount,count);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> ivec;
        int mNum = 1,cNum=1,pre = -INT_MAX;
        if(root == nullptr) return ivec;
        dfs(root,ivec,pre,mNum,cNum);
        return ivec;

    }
};

//普通遍历解法
class Solution {
public:
    //先使用map将值按照频率进行存储键值对，然后按照频率从大到小排序，然后就可以选择首部元素
    void dfs(TreeNode* root,unordered_map<int,int>& tMap){
        if(root == nullptr) return;
        dfs(root->left,tMap);
        tMap[root->val]++;
        dfs(root->right,tMap);
        return;
    }
    bool static cmp(const pair<int,int>& l, const pair<int,int>& r){
        return l.second > r.second;
    }
    vector<int> findMode(TreeNode* root) {
        unordered_map<int,int> imap;
        vector<int> res;
        if(root == nullptr) return res;
        dfs(root,imap);
        //使用vector存储键值对，方便进行排序后的处理
        vector<pair<int, int>> vec(imap.begin(), imap.end());
        
        sort(vec.begin(),vec.end(),cmp);
        res.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) res.push_back(vec[i].first);
            else break;
        }
        return res;

    }
};


// 记录一下Morris 中序遍历，可以实现O（1）空间复杂度
TreeNode *cur = root, *pre = nullptr;
while (cur) {
    if (!cur->left) {
        // ...遍历 cur
        cur = cur->right;
        continue;
    }
    pre = cur->left;
    while (pre->right && pre->right != cur) {
        pre = pre->right;
    }
    if (!pre->right) {
        pre->right = cur;
        cur = cur->left;
    } else {
        pre->right = nullptr;
        // ...遍历 cur
        cur = cur->right;
    }
}